package com.c2b.algorithm.leetcode.base;

/**
 * <b>二维数组中的查找</b>
 * <p>在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。<br>
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。</p>
 *
 * <pre>
 *     示例:
 *
 *      现有矩阵 matrix 如下：
 *      [
 *          [1,   4,  7, 11, 15],
 *          [2,   5,  8, 12, 19],
 *          [3,   6,  9, 16, 22],
 *          [10, 13, 14, 17, 24],
 *          [18, 21, 23, 26, 30]
 *      ]
 *      给定 target = 5，返回 true。
 *      给定 target = 20，返回 false。
 *
 *      限制：
 *          0 <= n <= 1000
 *          0 <= m <= 1000
 * </pre>
 *
 * @author c2b
 * @since 2023/3/6 17:15
 */
public class LC0004FindNumberIn2DArray {

    /**
     * 取矩阵右上角的元素作为标准，并进行比较，如果目标值大于标准则“行加一”，如果目标值小于标准则“列减一”。
     * <p>复杂度分析：
     * 时间复杂度 O(M+N) ：其中，N 和 M 分别为矩阵行数和列数，此算法最多循环 M+N 次。
     * 空间复杂度 O(1) : i, j 指针使用常数大小额外空间。
     * </p>
     */
    public static boolean findNumberIn2DArray(final int[][] matrix, final int target) {
        //先判断数组是否为空，包括一维数组判空和二维数组判空
        if (matrix == null || matrix.length == 0 || matrix[0].length < 1) {
            return false;
        }
        // 至少有一行一列（取矩阵右上角的元素作为标准，并进行比较，如果目标值大于标准则“行加一”，如果目标值小于标准则“列减一”。）
        // 当前行
        int curRow = 0;
        // 当前列
        int curCol = matrix[0].length - 1;
        while (curRow < matrix.length && curCol >= 0) {
            if (target > matrix[curRow][curCol]) {
                curRow++;
            } else if (target < matrix[curRow][curCol]) {
                curCol--;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] ints = {
                {1, 1}
        };

        System.out.println(findNumberIn2DArray(ints, 2));
    }
}
